The invention generally relates to the field of image recognition.
Image recognition is important in many fields, including automatic data collection, for example bar code reading. The ability to capture image data at higher resolutions leads to a need for faster processing of the captured image data.
Some aspects of the invention concern a process for detection of straight-line segments in a stream of digital data that are representative of an image having dimension (m, n) and size T=mxc3x97n, in which the contour points of said image each defined by the modulus and the orientation of their gradient in relation to a horizontal axis are identified. It extends to a device for detection of straight-line segments for implementing this detection process.
In one aspect, a process for detection of straight-line segments can permit processing of the digital data that are representative of a high-resolution image at a very elevated rate, supplying the start and end coordinates and the orientation of each of said straight-line segments.
Such a process is applied, in particular, for the detection of straight-line segments in a stream of digital data that are representative of images of codes in one and two dimensions which are formed on an electronic sensor such as a photosensitive matrix. To this end, the process may be implemented in a detection device which is integrated within a processing submodule forming an image acquisition and processing subassembly to process images of codes which are formed on a photosensitive matrix, such as described in the French patent application (French Serial No. 99.00717 filed on Jan. 22, 1999) filed in the name of the applicant, the processing submodule can employ cabled processing units comprising, upstream of said detection device:
a replicate-sampling circuit capable of reducing the size T of the image formed on the photosensitive matrix, for example by dividing said size T in accordance with the pyramidal method of BURT so as to obtain an image of reduced size T/4 and then T/16; and
a contour detection circuit to detect the contours in the reduced image emitted from the replicate-sampling circuit, adapted to supply images of said contours in which the contour points are defined by the modulus and the orientation of their gradient in relation to a horizontal axis, where the gradient represents the magnitude of the contrast between two points. These contour points are determined, for example, by calculating the gradients by application of the masks method of ROBERTS in the horizontal and vertical directions and by retaining as contour points the sole points for which the modulus of the gradient is greater than a predetermined threshold and maximal in the direction of said gradient which is defined by the argument of the latter, the other points being considered as not pertaining to a contour and being identified, for example, by a value such as xe2x88x921 of the orientation of their gradient.
Another aspect of the invention provides, for each image, a histogram of the orientations of the various straight-line segments detected.
The process for detection of straight-line segments according to the invention can be characterized in that the stream of digital data is stored in the form of two successive lines, each of n points P(i, j), with 1xe2x89xa6ixe2x89xa6m and nxe2x89xa67xe2x89xa6j, and for each of the lines the n points of said line are extracted successively, and for each point Pc(i, j) extracted, the so-called current point:
the three points having inferior coordinates Pa(ixe2x88x921, jxe2x88x921), Pb(i, jxe2x88x921), Pd(ixe2x88x921, j) directly neighbouring said current point are extracted,
successively the value of the orientation of the gradient of the current point Pc are compared with that of the neighbouring points Pa, Pb and Pd, and the values of the orientations of the gradients of the points Pb and Pd are compared,
the result of a comparison, representative of a connection between two points, is validated if said points are contour points and if the difference between the values of the orientation of their gradient is less than or equal to a predetermined value k,
when the result of a comparison is validated the coordinates of the point of the connection having inferior coordinates, the so-called start-point, are copied over to those of the point of said connection having superior coordinates, the so-called end-point, and the coordinates of the start-point are erased from the memory, unless said start-point has been identified as being an origin point of a straight-line segment.
it is verified whether solely the point Pa (ixe2x88x921, jxe2x88x921) is a contour point amongst the four points Pa, Pb, Pc, Pd extracted, and in the affirmative case the size of the straight-line segment for which said point Pa is the final point is calculated and the coordinates of the origin point and of the final point and the orientation of said straight-line segment, if its size is greater than a predetermined threshold, are saved.
This process therefore operates on the basis of line memories corresponding to successive lines of the image and permitting the whole of said image to be scanned from top to bottom, said memories on the one hand containing the result of the detection of contours, that is to say, for each point the value of the orientation of its gradient (equal to a given value if the point is a contour point and to xe2x88x921 in the contrary case), and on the other hand serving to write the coordinates of the extremities, the origin point and final point, and the orientation of the straight-line segments.
Moreover, the obtaining of a series of straight-lines segments from a contour consists in following this contour from the xe2x80x9chighestxe2x80x9d point as far as the xe2x80x9clowestxe2x80x9d point thereof and in deciding, firstly, for each point P(i, j) containing a contour, whether P pertains to a neighbouring segment S, itself constituted by one or more contour points. Then if P pertains to the segment S the final extremity of this segment takes as its coordinates those of P, that is to say (i, j), the origin extremity of said segment remaining unchanged and the coordinates of the possible intermediate points being erased. On the other hand, if P does not pertain to this segment it then defines the origin of a new segment, the two extremities of which are equal to (i, j), the size of which is equal to I and the orientation of which is xcex8,P.
Such a detection process may permit processing at a higher ratexe2x80x94equivalent, for example, to the pixel frequency at which data that are representative of images are supplied by a photosensitive matrixxe2x80x94of the digital data that are representative of the contours of high-resolution images.
According to a particular embodiment which is directed towards the processing of horizontal or substantially horizontal straight-line segments:
at the time of the validation of a first connection between two neighbouring points P(ixe2x88x921, j), P(i, j) pertaining to the same line, representative of an initial horizontal straight-line segment, the coordinates of the start-point of the connection are replaced by those of the- end-point of said connection, and conversely those of the end-point are replaced by those of the start-point.
then, for any point P(i+x,j) pertaining to said line, connected to the initial straight-line segment, the coordinates of said point are replaced by the initial coordinates (ixe2x88x921, j) of the origin point of the initial horizontal straight-line segment and the coordinates of said origin point are replaced by those (i+x, j) of said point.
Moreover, and in advantageous manner, at the time of the validation of the connection between a point
P(i, j) with a point P(ixe2x88x921, jxe2x88x921) or P(i+1, jxe2x88x921) validated as an extremity point, origin or final, of a horizontal straight-line segment, the coordinates of said point P(i, j) are transferred to those of the opposing extremity point, final or origin, of said straight-line segment, and those of said opposing extremity point are transferred to those of said point P(i, j).
According to these measures, in the case of horizontal or substantially horizontal straight-line segments the two extremities of said segments are revealed, for said extremities are both susceptible of being connected to another segment of a size greater than or equal to one which is processed in the following line. For this reason the process according to the invention permits two horizontal segments to be connected, the coordinates of the neighbouring extremities of these segments being erased, whereas the coordinates of the opposing extremities of said segments are transferred reciprocally from one extremity to the other.
Moreover, the process likewise permits a horizontal straight-line segment to be connected with a contour point, the coordinates of said contour point and those of the extremity of the straight-line segment opposing said contour point being transferred in reciprocal manner.
Furthermore, the histogram of the orientations of the various straight-line segments detected in the image is advantageously calculated.
By way of example, such a histogram of the orientations presents interest, in particular, in the case of the reading of codes in one dimension which are composed of parallel bars, for it then exhibits a peak corresponding to the value xcex8 of the angle between the horizontal and the axis of said parallel bars. For this reason, data that are i representative of the code are easily obtained by performing a xe2x80x9creadingxe2x80x9d of said code along a line which is orthogonal to that defined by the angle xcex8.
Such a histogram also presents interest within the context of two-dimensional codes exhibiting a specific signature such as, for example, the codes DATAMATRIX delimited by two straight orthogonal lines of the same length. In this case, such a code is easily identified by verification of the following two hypotheses: sizes of the two identical straight-line segments and difference of the values of the orientations corresponding to the peaks of the histogram substantially equal to 90xc2x0.
According to another characteristic of the invention, the contour points of the initial image (m, n) are defined by values of the orientation of the gradient amounting to between 0 and 15 which are obtained by a division of the trigonometric circle into 16 equal sectors and which are each representative of an angular position within one of said sectors.
Furthermore, on the basis of these values a connection is preferentially validated between two contour points by means of the following table:
use of the table consisting, on the one hand, in declaring the connection valid when the datum in said table corresponding to the intersection of the values xcex81, xcex82 of the orientations of the two contour points is different from xe2x88x921, and on the other hand in conferring on the end-point of the connection an orientation value equal to that of said datum.
According to another aspect of the invention, the stream of digital data is stored in a memory comprising three block memories, each of a capacity of n points, capable of permitting, by circular permutation of said block memories, the storage of n points in a block memory and simultaneously the processing of the data contained in the other two block memories.
The invention extends to a device for detection of straight-line segments in a stream of digital data which are supplied at a pixel frequency and which are representative of an image (m, n) in which the contour points of said image are identified. According to the invention this detection device comprises:
a data storage for storing the stream of digital data in the form of successive lines each consisting of n data items,
a buffer circuit comprising:
registers for successive reading of the digital data to be processed,
registers for storing the results of the processing of the digital data, representative of the coordinates of the extremity points and of the orientation of the straight-line segments,
and working registers,
a management module receiving a clock signal that is representative of the pixel frequency of supply of the digital data, said management module being linked to the data storage and to the buffer circuit and being adapted, on the one hand, to manage the padding and the processing at the pixel frequency of the digital data in the data storage and on the other hand the reciprocal exchange of data between the data storage and the buffer circuit,
a programmed calculation module for performing tests intended for the processing of the digital data in the reading registers,
and a sequencer which receives a clock signal that is representative of the pixel frequency and which is adapted, as a function of the results supplied by the calculation module, to control the management module and the buffer circuit with a view to the transfers of data between said buffer circuit and the data storage.
Moreover, and in advantageous manner, the data storage comprises three block memories each capable of storing a line of n digital data items, the management module being adapted to control a circular permutation of said memory blocks which is capable of permitting the storage of n data items in a block memory and simultaneously the processing of the data contained in the other two block memories.
Furthermore, this detection device advantageously comprises a calculation module which receives the results stored in the storage registers and representative of the orientations of the straight-line segments detected and which is programmed to calculate the histogram of said orientations.